package ch02Sort;
//归并排序
/*
归并排序将两个有序的子数组归并后，该数组就有序了
 */
public class Merge extends Sort {
    public static Comparable[] aux;
    //排序入口
    public static void sort(Comparable[] a) {
        int n = a.length;
        aux = new Comparable[n];
        sort(a,0,n-1);
    }
    /*
    递归排序到递归尽头 即左右数组只有一个元素，
    通过merge将两个数组合并成有序数组，
    以此类推merge成最终的有序数组
     */
    public static void sort(Comparable[] a, int lo, int hi) {
        int mid = lo + (hi-lo)/2;
        if(lo==hi) return;
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        merge(a,lo,hi);
    }
    //对子数组排序，借用辅助数组aux
    public static void merge(Comparable[] a, int lo, int hi) {
        int mid = lo+ (hi-lo)/2;
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k];
        }
        int i = lo;
        int j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if (i > mid) {
                a[k] = aux[j++];
            } else if (j > hi) {
                a[k] = aux[i++];
            }else if (less(aux[j], aux[i])) {
                a[k] = aux[j++];
            }else {
                a[k] = aux[i++];
            }
        }
    }

    public static void main(String[] args) {

        sort(Sort.a);
        System.out.print("现数组：");
        show(Sort.a);
        System.out.print("isSorted？");
        System.out.println(isSorted(Sort.a));

    }
}
